from typing import List

"""
超时了。。。
"""


class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        res = 0
        dp = [0] * len(prices)

        for i in range(len(prices) - 1):
            for j in range(i + 1, len(prices)):
                dp[j] = max(dp[i] + prices[j] - prices[i] - fee, dp[j - 1], dp[j])
                print(i, j, dp)
        return dp[-1]


if __name__ == "__main__":
    res = Solution().maxProfit([1, 3, 2, 8, 4, 9], 2)
    print(res)
